class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
        vector<vector<int>> ret;
        sort(nums.begin(), nums.end());
        
        int n = nums.size();
        for(int a = 0; a < n; )
        {
            for(int b = a + 1; b < n; )
            {
                long long target2 = (long long)target - nums[a] - nums[b];
                int left = b + 1, right = n - 1;
                while(left < right)
                {
                    if(nums[left] + nums[right] < target2)
                    {
                        ++left;
                    }
                    else if(nums[left] + nums[right] > target2)
                    {
                        --right;
                    }
                    else
                    {
                        ret.push_back({nums[a],nums[b],nums[left++],nums[right--]});
                        while(left < right && nums[left] == nums[left-1])
                        {
                            ++left;
                        }
                        while(left < right && nums[right] == nums[right+1])
                        {
                            --right;
                        }
                    }
                }
                ++b;
                while(b < n && nums[b] == nums[b-1])
                {
                    ++b;
                }
            }
            ++a;
            while(a < n && nums[a] == nums[a-1])
            {
                ++a;
            }
        }
        return ret;
    }
};